import macros, strutils, os, json, tables, sets, sugar, hashes, std/compilesettings, sequtils, pathnorm
import macroutils except Lit
import pkg/nimbleutils

const
  Stringable = {nnkStrLit..nnkTripleStrLit, nnkCommentStmt, nnkIdent, nnkSym}
  builtins = ["addr", "and", "as", "asm",
    "bind", "block", "break",
    "case", "cast", "concept", "const", "continue", "converter",
    "defer", "discard", "distinct", "div", "do",
    "elif", "else", "end", "enum", "except", "export",
    "finally", "for", "from", "func",
    "if", "import", "in", "include", "interface", "is", "isnot", "iterator",
    "let",
    "macro", "method", "mixin", "mod",
    "nil", "not", "notin",
    "object", "of", "or", "out",
    "proc", "ptr",
    "raise", "ref", "return",
    "shl", "shr", "static",
    "template", "try", "tuple", "type",
    "using",
    "var",
    "when", "while",
    "xor",
    "yield"]
  # The following list is generated by running `jq '.entries[] | select (.type == "skType").name'` on the output of `nim jsondoc system.nim`
  systemTypes = ["int", "int8", "int16", "int32", "int64", "uint", "uint8",
    "uint16", "uint32", "uint64", "float", "float32", "float64", "char",
    "string", "cstring", "pointer", "typedesc", "`ptr`", "`ref`", "void",
    "auto", "any", "untyped", "typed", "bool", "SomeSignedInt",
    "SomeUnsignedInt", "SomeInteger", "SomeFloat", "SomeNumber", "SomeOrdinal",
    "`static`", "`type`", "TypeOfMode", "iterable", "Ordinal", "range",
    "array", "openArray", "varargs", "seq", "set", "UncheckedArray", "sink",
    "lent", "HSlice", "Slice", "byte", "Natural", "Positive", "RootObj",
    "RootRef", "RootEffect", "StackTraceEntry", "Exception", "Defect",
    "CatchableError", "JsRoot", "owned", "Endianness", "TaintedString",
    "csize", "AllocStats", "GC_Strategy", "PFrame", "TFrame", "ForeignCell",
    "Channel", "BackwardsIndex", "NimNode", "ForLoopStmt"]
  syspaths {.strdefine.} = ""
  nodeclguards = defined(nodeclguards)
  noopaquetypes = defined(noopaquetypes)
  exportall = defined(exportall) or nodeclguards
  opirRebuild = defined(opirRebuild)
  futharkRebuild = defined(futharkRebuild) or opirRebuild
  preAnsiFuncDecl = defined(preAnsiFuncDecl)
  echoForwards = defined(echoForwards)
  generateInline = defined(generateInline)
  VERSION = block:
    # source style, go up one dir
    var nimblePath = currentSourcePath().parentDir().parentDir() / "futhark.nimble"
    if not fileExists(nimblePath):
      # installed style, nimble file in same dir
      nimblePath = currentSourcePath().parentDir() / "futhark.nimble"
    if not fileExists(nimblePath):
      # try find by name
      nimblePath = "futhark"
    try:
      $getPackage(nimblePath).version
    except CatchableError:
      warning "Couldn't find futhark version from 'nimble dump " & nimblePath & "'"
      "unknown"

# This is to allow cross-compilation to non-windows targets on windows
when not declared(buildOS):
  const buildOS {.magic: "BuildOS".}: string = hostOS
const windowsHost = buildOS == "windows"
const cmdPrefix = when windowsHost: "cmd /E:ON /C " else: ""

func hostQuoteShell(s: string): string =
  ## Quote ``s``, so it can be safely passed to shell.
  when not defined(windows) and windowsHost:
    result = quoteShellWindows(s)
  else:
    result = quoteShell(s)

template endsWith(a: string, b: set[char]): bool =
  a.len > 0 and a[^1] in b

proc hostJoinPathImpl(result: var string, state: var int, tail: string) =
  let trailingSep = tail.endsWith({'\\', DirSep, AltSep}) or tail.len == 0 and result.endsWith({'\\', DirSep, AltSep})
  normalizePathEnd(result, trailingSep=false)
  addNormalizePath(tail, result, state, '\\')
  normalizePathEnd(result, trailingSep=trailingSep)

proc hostJoinPath(head, tail: string): string =
  ## Joins two directory names to one.
  ##
  ## returns normalized path concatenation of `head` and `tail`, preserving
  ## whether or not `tail` has a trailing slash (or, if tail if empty, whether
  ## head has one).
  ##
  ## See also:
  ## * `joinPath(varargs) proc <#joinPath,varargs[string]>`_
  ## * `/ proc <#/,string,string>`_
  ## * `splitPath proc <#splitPath,string>`_
  ## * `uri.combine proc <uri.html#combine,Uri,Uri>`_
  ## * `uri./ proc <uri.html#/,Uri,string>`_
  when not defined(windows) and windowsHost:
    result = newStringOfCap(head.len + tail.len)
    var state = 0
    hostJoinPathImpl(result, state, head)
    hostJoinPathImpl(result, state, tail)
  else:
    joinPath(head, tail)

proc hostIsAbsolute(path: string): bool =
  ## Checks whether a given `path` is absolute.
  if len(path) == 0: return false

  when not defined(windows) and windowsHost:
    var len = len(path)
    result = (path[0] in {'/', '\\'}) or
              (len > 1 and path[0] in {'a'..'z', 'A'..'Z'} and path[1] == ':')
  else:
    result = isAbsolute(path)

proc hostAbsolutePath(path: string, root = getCurrentDir()): string =
  ## Returns the absolute path of `path`, rooted at `root` (which must be absolute;
  ## default: current directory).
  ## If `path` is absolute, return it, ignoring `root`.
  if hostIsAbsolute(path): path
  else:
    if not root.hostisAbsolute:
      raise newException(ValueError, "The specified root is not absolute: " & root)
    hostJoinPath(root, path)

proc hostCreateDir(dir: string) =
  # createDir(dir)
  if dirExists(dir): return
  when windowsHost:
    discard staticExec(cmdPrefix & "mkdir " & dir.replace("/", "\\").hostQuoteShell())
  else:
    discard staticExec("mkdir -p " & dir.hostQuoteShell())
  assert dirExists(dir), "Unable to create directory " & dir

template strCmp(node, value: untyped): untyped = node.kind in Stringable and node.strVal == value

proc exportMark(n: NimNode): NimNode =
  when exportall:
    n.postfix "*"
  else:
    n

type
  SymbolKind* = enum
    Anon = "anon"
    Argument = "arg"
    Proc = "proc"
    Struct = "struct"
    Union = "union"
    Enum = "enum"
    EnumVal = "enumval"
    Typedef = "typedef"
    Field = "field"
    Variable = "var"
    Const = "const"
  PragmasCallback = proc(name: string, kind: SymbolKind, pragmas: var seq[NimNode])
  RenameCallback = proc(name: string, kind: SymbolKind, partof: string, overloading: var bool): string
  OpirCallbacks = seq[proc(opirOutput: JsonNode): JsonNode]
  Forward = object
    name: string
    extraPragmas: seq[string]
  State = object
    entities: OrderedTable[string, JsonNode]
    opaqueTypes: HashSet[string]
    retypes: Table[string, Table[string, NimNode]]
    fieldRenames: Table[string, Table[string, string]]
    typeDefMap: Table[string, NimNode]
    typeNameMap: Table[string, NimNode]
    renamed: Table[string, string]
    usedNames: HashSet[string]
    used: OrderedSet[string]
    knownValues: HashSet[string]
    types: Table[string, NimNode]
    procs: Table[string, NimNode]
    extraTypes: Table[string, NimNode]
    explicitImports: Table[string, HashSet[string]]
    imports: Table[string, HashSet[string]]
    renameCallback: RenameCallback
    pragmasCallback: PragmasCallback
    forwards: seq[Forward]
    files: seq[string]
    currentFile: string
    overloading: Table[string, bool]

proc declGuard(state: State, name, decl: NimNode): NimNode =
  when nodeclguards:
    decl
  else:
    if state.overloading.getOrDefault(name.strVal, false):
      decl
    else:
      superQuote do:
        when not declared(`name`):
          `decl`
        else:
          static: hint("Declaration of " & `name.strVal` & " already exists, not redeclaring")

proc addExtraType(state: var State, file: string, node: NimNode) =
  let file = if file in state.files: file else: ""
  state.extraTypes.mgetOrPut(file, newStmtList()).add node

proc addType(state: var State, file: string, node: NimNode) =
  let file = if file in state.files: file else: ""
  state.types.mgetOrPut(file, newNimNode(nnkTypeSection)).add node

proc addProc(state: var State, file: string, node: NimNode) =
  let file = if file in state.files: file else: ""
  state.procs.mgetOrPut(file, newStmtList()).add node

proc isUnsignedNumber(x: string): bool =
  try:
    discard parseBiggestUInt(x)
    result = true
  except ValueError:
    result = false

proc sanitizeName(usedNames: var HashSet[string], origName: string, kind: SymbolKind, renameCallback: RenameCallback, partof: string, overloading: var Table[string, bool]): string {.compileTime.} =
  result = origName
  var overloadingState = false
  if not renameCallback.isNil:
    result = result.renameCallback(kind, partof, overloadingState)

  # These checks should ensure that valid C names which are invalid Nim names get renamed
  if result.startsWith("_"):
    if result.startsWith("__"):
      result = "compiler_" & result[2..^1]
    else:
      result = "internal_" & result[1..^1]
  if result.endsWith("_"):
    result = result & "private"
  while (let oldLen = result.len; result = result.replace("__", "_"); result.len != oldLen): discard

  # These should ensure all identifiers are unique in Nim
  var
    normalizedName = result.nimIdentNormalize()
    renamed = false
  if (usedNames.contains(normalizedName) and not overloadingState) or (normalizedName in builtins) or (kind == Typedef and normalizedName in systemTypes):
    result.add "_" & $kind
    normalizedName.add $kind
    renamed = true
  if (usedNames.contains(normalizedName) and not overloadingState) or (normalizedName in builtins) or (kind == Typedef and normalizedName in systemTypes):
    let uniqueTail = hash(origName).uint32.toHex
    result.add "_" & uniqueTail
    normalizedName.add uniqueTail
    renamed = true
  if renamed:
    hint "Renaming \"" & origName & "\" to \"" & result & "\"" & (if partof.len != 0: " in " & partof else: "")
  usedNames.incl normalizedName
  overloading[result] = overloadingState

proc sanitizeName(state: var State, origName: string, kind: SymbolKind): string {.compileTime.} =
  if not state.renamed.hasKey(origName):
    result = sanitizeName(state.usedNames, origName, kind, state.renameCallback, partof = "", state.overloading)
    state.renamed[origName] = result
  else:
    result = state.renamed[origName]

proc sanitizeName(state: var State, x: JsonNode): string {.compileTime.} =
  state.sanitizeName(x["name"].str, x["kind"].str.parseEnum[:SymbolKind])

proc findAlias(kind: JsonNode): string =
  case kind["kind"].str:
  of "alias": kind["value"].str
  of "base", "special", "vector": ""
  of "pointer", "atomic": findAlias(kind["base"])
  of "array": (if kind["value"].kind == JNull: "" else: findAlias(kind["value"]))
  of "struct", "union", "enum": (if kind.hasKey("name"): kind["name"].str else: "")
  of "proc": (if kind.hasKey("name"): kind["name"].str else: "")
  else: error("Unknown kind in findAlias: " & $kind)

proc addUsings(used: var OrderedSet[string], node: JsonNode) =
  case node["kind"].str:
  of "proc":
    let alias = node["return"].findAlias
    if alias.len != 0:
      used.incl alias
    for arg in node["arguments"]:
      var alias: string
      if arg.hasKey("type"):
        used.addUsings arg["type"]
        alias = arg["type"].findAlias
      else:
        used.addUsings arg
        alias = arg.findAlias
      if alias.len != 0:
        used.incl alias
  of "struct", "union":
    for field in node["fields"]:
      if field["type"].kind != JNull:
        case field["type"]["kind"].str:
        of "struct", "union", "pointer", "proc":
          used.addUsings field["type"]
        let alias = field["type"].findAlias
        if alias.len != 0:
          used.incl alias
  of "typedef":
    let alias = node["type"].findAlias
    if alias.len != 0:
      used.incl alias
    used.addUsings(node["type"])
  of "pointer", "atomic":
    let alias = node["base"].findAlias
    if alias.len != 0:
      used.incl alias
    elif node["base"]["kind"].str == "proc":
      used.addUsings(node["base"])
  of "alias":
    used.incl node.findAlias
  of "enum", "base", "special", "vector": discard
  of "array":
    used.addUsings(node["value"])
  of "var":
    used.addUsings(node["type"])
  of "const":
    if node["type"]["kind"].str != "unknown":
      used.addUsings(node["type"])
  else: error("Unknown node in addUsings: " & $node)

proc addKnown(state: var State, known: string) =
  state.knownValues.incl state.renamed[known]
  state.opaqueTypes.excl known

proc addEntity(state: var State, name: string, entity: JsonNode) =
  state.entities[name] = entity
  state.opaqueTypes.excl name

proc addOpaque(state: var State, opaque: string) =
  if not state.entities.hasKey(opaque) and opaque notin builtins and opaque notin systemTypes:
    state.opaqueTypes.incl opaque

proc toNimType(json: JsonNode, state: var State): NimNode =
  result = case json["kind"].str:
    of "base": json["value"].str.ident
    of "pointer":
      var node =
        case json["base"]["kind"].str:
        of "alias", "proc", "base":
          var node = json["base"].toNimType(state)
          if node.strCmp "void":
            node = "pointer".ident
          node
        else:
          "pointer".ident
      for i in 0..<json["depth"].num - (if node.strCmp("pointer") or json["base"]["kind"].str == "proc": 1 else: 0):
        node = nnkPtrTy.newTree(node)
      node
    of "proc":
      var procTy = nnkProcTy.newTree(
        nnkFormalParams.newTree(json["return"].toNimType(state)),
        nnkPragma.newTree(json["callingConvention"].str.ident))
      if json["variadic"].bval and (json["proto"].bval or preAnsiFuncDecl):
        procTy[^1].add "varargs".ident
      if json["return"]["kind"].str == "pointer" and json["return"]["base"]["kind"].str == "alias":
        state.addOpaque json["return"]["base"]["value"].str
      var
        i = 0
        usedFields: HashSet[string]
      for arg in json["arguments"]:
        let
          aname = if arg.hasKey("name"): usedFields.sanitizeName(arg["name"].str, Argument, state.renameCallback, "", state.overloading) else: "a" & $i
          atype = (if arg.hasKey("type"): arg["type"] else: arg).toNimType(state)
        if arg.hasKey("type"):
          if arg["type"]["kind"].str == "pointer" and arg["type"]["base"]["kind"].str == "alias":
            state.addOpaque arg["type"]["base"]["value"].str
        procTy[0].add nnkIdentDefs.newTree(aname.ident, atype, newEmptyNode())
        inc i
      procTy
    of "array":
      if json.hasKey("size"):
        nnkBracketExpr.newTree("array".ident, json["size"].num.newLit, json["value"].toNimType(state))
      else:
        nnkPtrTy.newTree(nnkBracketExpr.newTree("UncheckedArray".ident, json["value"].toNimType(state)))
    of "alias":
      if not state.knownValues.contains json["value"].str:
        state.addOpaque json["value"].str
      state.typeNameMap[json["value"].str]
    of "enum":
      error "Unable to resolve nested enums from here"
    of "struct", "union":
      error "Unable to resolve nested struct/union from here"
    of "vector":
      nnkObjectTy.newTree(newEmptyNode(), newEmptyNode(), newEmptyNode())
    of "special":
      nnkTupleTy.newTree(
        newIdentDefs("low".ident, "uint64".ident),
        newIdentDefs("high".ident, (if json["value"].str == "uint128": "uint64" else: "int64").ident))
    of "atomic":
      state.imports.mgetOrPut(state.currentFile, initHashSet[string]()).incl "std/atomics"
      nnkBracketExpr.newTree("Atomic".ident, json["base"].toNimType(state))
    else:
      warning "Unknown: " & $json
      "pointer".ident

proc createEnum(origName: string, node: JsonNode, state: var State, comment: string) =
  if node["fields"].len == 0:
    warning "Ignoring empty enum: " & origName
    return
  let
    origNameIdent = origName.ident
    name = state.typeDefMap.getOrDefault(origName, origNameIdent) #state.sanitizeName(origName, "enum").ident
    baseType = node["base"].toNimType(state)
  var
    enumTy = nnkEnumTy.newTree(newEmptyNode())
    values: OrderedTable[int, NimNode]
    consts = newStmtList()
  for field in node["fields"]:
    let
      value = parseInt(field["value"].str)
      fname = state.sanitizeName(field["name"].str, EnumVal).ident
    if origName.len == 0:
      consts.add state.declGuard(fname, superQuote do:
        const `fname`* = `baseType`(`newLit(value)`))
    else:
      if not values.hasKey(value):
        values[value] = fname
      else:
        consts.add state.declGuard(fname, superQuote do:
          const `fname`* = `name`.`values[value]`)
    state.addKnown field["name"].str
  if origName.len != 0:
    values.sort(system.cmp)
    for value, name in values:
      enumTy.add nnkEnumFieldDef.newTree(name, value.newLit)
    var typedef = parseStmt("""
    type
      dummy = enum ## """ & comment & """
        ## This doesn't work for some reason
        dummy""")[0][0]

    var pragmas = @[nnkExprColonExpr.newTree("size".ident, nnkCall.newTree("sizeof".ident, baseType))]
    if not state.pragmasCallback.isNil:
      state.pragmasCallback(origName, Enum, pragmas)

    typedef[0] = nnkPragmaExpr.newTree(name.postfix "*", nnkPragma.newTree(pragmas))
    typedef[2] = enumTy
    state.addExtraType(node["file"].str, quote do:
      type
        `name`* {.size: sizeof(`baseType`).} = `enumTy`)
  state.addExtraType(node["file"].str, consts)

proc createStruct(origName, saneName: string, node: JsonNode, state: var State, comment: string) =
  let name = block:
    let coreName = state.typeDefMap.getOrDefault(origName, origName.ident).exportMark
    var pragmas =
      if node["kind"].str == "union":
        @[ident"union", ident"bycopy"]
      else:
        @[ident"pure", ident"inheritable", ident"bycopy"]

    if node.hasKey("packed") and node["packed"].bval == true:
      pragmas.add "packed".ident

    if not state.pragmasCallback.isNil:
      state.pragmasCallback(origName, if node["kind"].str == "union": Union else: Struct, pragmas)

    if pragmas.len > 0:
      nnkPragmaExpr.newTree(coreName, nnkPragma.newTree(pragmas))
    else:
      coreName
  # This is a bit of a hack, but the only way to get a comment into an object..
  var newType = parseStmt("""
  type
    dummy = object
      ## """ & comment)[0][0]
  newType[0] = name
  var
    lastFieldType: JsonNode
    usedFieldNames: HashSet[string]
    anons = 0
  for field in node["fields"]:
    if field.hasKey("bitsize") and field["bitsize"].num == 0: continue
    let fieldType =
      if field["type"].kind == JNull:
        lastFieldType
      elif field["type"]["kind"].str == "array" and field["type"]["value"].kind == JNull:
        var nFieldType = field["type"]
        nFieldType["value"] = lastFieldType
        nFieldType
      else:
        field["type"]
    let (saneFieldName, fname) =
      if field.hasKey("name") and field["name"].str.len != 0:
        let
          saneFieldName = usedFieldNames.sanitizeName(field["name"].str, Field, state.renameCallback, partof = saneName, state.overloading)
          fname =
            if state.fieldRenames.hasKey(origName):
              state.fieldRenames[origName].getOrDefault(field["name"].str, saneFieldName)
            else: saneFieldName
        (saneFieldName, fname)
      else:
        let name = usedFieldNames.sanitizeName("anon" & $anons, Field, state.renameCallback, partof = saneName, state.overloading)
        inc anons
        (name, name)
    let fident =
      if node.hasKey("alignment"):
        nnkPragmaExpr.newTree(fname.ident.postfix "*", nnkPragma.newTree(nnkCall.newTree("align".ident, newLit(node["alignment"].num))))
      elif field.hasKey("bitsize"):
        nnkPragmaExpr.newTree(fname.ident.postfix "*", nnkPragma.newTree(nnkExprColonExpr.newTree("bitsize".ident, newLit(field["bitsize"].num))))
      else:
        fname.ident.postfix "*"
    if state.retypes.hasKey(saneName) and state.retypes[saneName].hasKey(fname):
      newType[^1][^1].add newIdentDefs(fident, state.retypes[saneName][fname])
    else:
      if fieldType["kind"].str == "pointer" and fieldType["base"]["kind"].str == "alias":
        state.addOpaque fieldType["base"]["value"].str
      if fieldType["kind"].str == "enum":
        let enumName = saneName & "_" & fname & "_t"
        createEnum(enumName, fieldType, state, "")
        newType[^1][^1].add newIdentDefs(fident, enumName.ident)
      elif fieldType["kind"].str in ["struct", "union"]:
        let
          structName = saneName & "_" & fname & "_t"
        createStruct(structName, structName, fieldType, state, "")
        newType[^1][^1].add newIdentDefs(fident, structName.ident)
      elif fieldType["kind"].str == "array" and fieldType["value"]["kind"].str in ["struct", "union"]:
        let
          structName = saneName & "_" & fname & "_t"
        createStruct(structName, structName, fieldType["value"], state, "")
        # Kind of a hack, rename the array to a base kind to just have it use the name directly
        var generated = fieldType
        generated["value"] = %*{"kind": "base", "value": structName}
        newType[^1][^1].add newIdentDefs(fident, generated.toNimType(state))
      else:
        newType[^1][^1].add newIdentDefs(fident, fieldType.toNimType(state))
    #else:
    #  if fieldType["kind"].str in ["struct", "union"] and fieldType.hasKey("name"):
    #    if not state.entities.hasKey(fieldType["name"].str):
    #      state.opaqueTypes.incl fieldType["name"].str
    #  else:
    #    warning "Unhandled anonymous field: " & $field
    lastFieldType = fieldType
  state.addType node["file"].str, newType

proc createProc(origName: string, node: JsonNode, state: var State) =
  if node["inlined"].getBool and not generateInline: return
  let nameIdent = state.renamed[origName].ident
  var
    def = node.toNimType(state)
    echoDef = false
    pragmas = def[1].children.toSeq
  block forwardBlock:
    for forward in state.forwards:
      if state.renamed[forward.name] == state.renamed[origName]:
        pragmas.add nnkExprColonExpr.newTree("exportc".ident, newLit(origName))
        if appType == "lib":
          pragmas.add "dynlib".ident
        for extra in forward.extraPragmas:
          let parsedPragmas = extra.parseExpr
          if parsedPragmas.kind == nnkTupleConstr:
            for pragma in parsedPragmas:
              pragmas.add pragma
          else:
            pragmas.add parsedPragmas
        if echoForwards:
          echoDef = true
        break forwardblock
    pragmas.add nnkExprColonExpr.newTree("importc".ident, newLit(origName))
  
  if not state.pragmasCallback.isNil:
    state.pragmasCallback(origName, Proc, pragmas)

  def = nnkProcDef.newTree(
    nameIdent.postfix "*",
    newEmptyNode(),
    newEmptyNode(),
    def[0],
    nnkPragma.newTree(pragmas),
    newEmptyNode(),
    newEmptyNode()
  )
  if echoDef: echo def.repr
  state.addProc node["file"].str,  state.declGuard(nameIdent, def)

proc createVar(origName: string, node: JsonNode, state: var State) =
  let
    nameIdent = state.renamed[origName].ident
    typeIdent = node["type"].toNimType(state)
    linkage = node["linkage"].str
  let pragmas: NimNode = case linkage:
    of "external": nnkPragma.newTree(nnkExprColonExpr.newTree("importc".ident, newLit(origName)))
    else: Empty()
  let pragmaExpr = nnkPragmaExpr.newTree(nameIdent.postfix "*", pragmas)
  state.addProc node["file"].str, state.declGuard(nameIdent, quote do:
    var `pragmaExpr`: `typeIdent`)

proc createConst(origName: string, node: JsonNode, state: var State, comment: string) =
  let
    nameIdent = state.renamed[origName].ident
    value =
      if node["type"]["kind"].str == "alias":
        if state.typeNameMap.hasKey(node["type"]["value"].str):
          node["type"].toNimType(state)
        else:
          state.renamed[node["type"]["value"].str].ident
      elif node["type"]["kind"].str == "unknown":
        if node["value"].kind == JInt:
          let intNode = newNimNode(nnkIntLit)
          intNode.intVal = node["value"].num
          intNode
        elif node["value"].kind == JFloat:
          let floatNode = newNimNode(nnkFloatLit)
          floatNode.floatVal = node["value"].fnum
          floatNode
        else: return
      elif node["type"]["kind"].str == "base":
        if node["type"]["value"].str == "cstring":
          newLit(node["value"].str)
        elif node["value"].kind == JInt:
          nnkCast.newTree(node["type"].toNimType(state), newLit(node["value"].num))
        elif node["value"].kind == JString and isUnsignedNumber(node["value"].str):
          # number did not fit in JInt so it was parsed as JString (uint64)
          nnkCast.newTree(node["type"].toNimType(state), newLit(parseUInt(node["value"].str)))
        else: return
      else: return
  let
    newConstValueStmt = parseStmt("const " & state.renamed[origName] & "* = " & value.repr & " ## " & comment)
    newLetValueStmt = parseStmt("let " & state.renamed[origName] & "* = " & value.repr & " ## " & comment)
  if node["type"]["kind"].str == "alias":
    if value == nameIdent: return
    let newConstTypeStmt = parseStmt("type " & state.renamed[origName] & "* = " & value.repr & " ## " & comment)
    let renamed = state.renamed.getOrDefault(node["type"]["value"].str, node["type"]["value"].str)
    if (state.typeNameMap.hasKey(renamed) or state.knownValues.contains renamed):
      state.addProc node["file"].str, state.declGuard(nameIdent, quote do:
        when `value` is typedesc:
          `newConstTypeStmt`
        else:
          when `value` is static:
            `newConstValueStmt`
          else:
            `newLetValueStmt`)
  else:
    state.addKnown origName
    state.addProc node["file"].str, state.declGuard(nameIdent, quote do:
      when `value` is static:
        `newConstValueStmt`
      else:
        `newLetValueStmt`)

proc createTypedef(origName: string, node: JsonNode, state: var State, comment: string) =
  var newType = parseStmt("type dummy = dummy ## " & comment)[0][0]
  newType[0] = state.typeDefMap[node["name"].str].exportMark
  var pragmas: seq[NimNode]
  if node["type"]["kind"].str == "vector":
    pragmas.add nnkExprColonExpr.newTree("importc".ident, newLit(origName))
  if not state.pragmasCallback.isNil:
    state.pragmasCallback(origName, Typedef, pragmas)
  if pragmas.len != 0:
    newType[0] = nnkPragmaExpr.newTree(newType[0], nnkPragma.newTree(pragmas))
  newType[^1] = node["type"].toNimType(state)
  if newType[^1].kind == nnkIdent and newType[^1].strVal == "void":
    return
  state.addType node["file"].str, newType
  var pointsTo = node["type"]
  if pointsTo["kind"].str == "pointer":
    pointsTo = pointsTo["base"]
  if pointsTo["kind"].str == "alias" and state.entities.hasKey(pointsTo["value"].str):
    pointsTo = state.entities[pointsTo["value"].str]
    if pointsTo.hasKey("file") and pointsTo["file"] != node["file"]:
      state.imports.mgetOrPut(node["file"].str, initHashSet[string]()).incl(
        pointsTo["file"].str.relativePath(node["file"].str.parentDir).changeFileExt("nim"))

proc createImport(node: JsonNode, state: var State) =
  if node["import"].str in state.files and node["file"].str in state.files:
    state.explicitImports.mgetOrPut(node["file"].str, initHashSet[string]()).incl node["import"].str.relativePath(node["file"].str.parentDir).changeFileExt("")

type
  FromTo = tuple[f, t: string]

proc getClangIncludePath*(): string =
  ## This tries to get the Clang include path used as `sysPath`. It requires
  ## Clang to be in your path, but should otherwise work well.
  const inclDir = staticExec("clang -print-resource-dir").strip() / "include"
  when dirExists(inclDir):
    inclDir
  else:
    {.warning: "futhark: clang include path not found".}
    ""

proc contains(a, b: NimNode): bool =
  for v in a:
    if v == b: return true

macro importc*(imports: varargs[untyped]): untyped =
  ## Generate code from C imports. String literals will be treated as files to
  ## `#include`. Paths can be added with `path <string literal>`, which are
  ## relative to your project folder, `absPath` can be used to supply absolute
  ## paths. Defines and undefines can be done with `define <name> <value>` and
  ## `undef <name>` respectively. Arguments for the compiler can be passed with
  ## `compilerarg <argument>`. To rename a structure or a field within a
  ## structure you can use `rename <name or name.field> <new name>`. And fields
  ## can be defined to have a different type with
  ## `retype <name.field> <new type>`, this is to allow more specific types to
  ## resolve `ptr`/`UncheckedArray` ambiguity and stricter types for e.g.
  ## overloading.
  result = newStmtList()
  var nodes = imports
  if imports[0].kind == nnkStmtList:
    nodes = imports[0]
  var
    defs = newLit("")
    outputPath = newLit("")
    files = nnkBracket.newTree()
    importDirs = nnkBracket.newTree()
    ignores = nnkBracket.newTree()
    cargs = nnkBracket.newTree()
    renames: seq[FromTo]
    retypes: seq[FromTo]
    renameCallback = newNilLit()
    pragmasCallback = newNilLit()
    opircallbacks = nnkPrefix.newTree(newIdentNode("@"), nnkBracket.newTree())
    forwards = nnkPrefix.newTree(newIdentNode("@"), nnkBracket.newTree())
    sysPathDefined = false
  for node in nodes:
    case node.kind:
    of nnkStrLit:
      defs = nnkInfix.newTree("&".ident, defs, newLit("#include \"" & node.strVal & "\"\n"))
      files.add newLit(node.strVal)
    of nnkCallKinds:
      case node[0].strVal.toLower:
      of "define":
        if node.len == 3:
          defs = nnkInfix.newTree("&".ident, defs, newLit("#define " & node[1].strVal & " " & node[2].repr & "\n"))
        else:
          defs = nnkInfix.newTree("&".ident, defs, newLit("#define " & node[1].strVal & "\n"))
      of "undef":
        defs = nnkInfix.newTree("&".ident, defs, newLit("#undef " & node[1].strVal & "\n"))
      of "path":
        let args = superQuote do: "-I" & hostQuoteShell(hostAbsolutePath(`node[1]`, getProjectPath()))
        assert args notin cargs, "path and syspath both handed the same path, or path given twice: " & node[1].repr
        cargs.add args
        importDirs.add superQuote do: hostAbsolutePath(`node[1]`, getProjectPath())
      of "syspath":
        let args = superQuote do: "-I" & hostQuoteShell(hostAbsolutePath(`node[1]`, getProjectPath()))
        assert args notin cargs, "syspath and path both handed the same path, or syspath given twice: " & node[1].repr
        cargs.add args
        sysPathDefined = true
      of "ignore":
        ignores.add superQuote do: hostAbsolutePath(`node[1]`, getProjectPath())
      of "compilerarg", "compilerargs":
        cargs.add node[1]
      of "rename":
        let
          f = if node[1].kind in Stringable: node[1].strVal else: node[1].repr
          t = if node[2].kind in Stringable: node[2].strVal else: node[2].repr
        renames.add (f: f, t: t)
      of "retype":
        assert node[1].kind == nnkDotExpr, "Retypes must target a field within an object"
        retypes.add (f: node[1].repr, t: node[2].repr)
      of "renamecallback":
        renameCallback = node[1]
      of "pragmascallback":
        pragmasCallback = node[1]
      of "addopircallback":
        opircallbacks[1].add node[1]
      of "outputpath":
        outputPath = node[1]
      of "forward":
        var extras = nnkPrefix.newTree(newIdentNode("@"), nnkBracket.newTree())
        for extra in 2..<node.len:
          extras[1].add newLit(node[extra].repr)
        forwards[1].add nnkObjConstr.newTree(bindSym("Forward"), nnkExprColonExpr.newTree("name".ident, node[1]), nnkExprColonExpr.newTree("extraPragmas".ident, extras))
      else:
        let toImport = genSym(nskConst)
        result.add quote do:
          const `toImport` = `node`
        defs = quote do: `defs` & ("#include " & `toImport` & "\n")
        files.add toImport
    else: error "Unknown argument passed to importc: " & $node.repr
  for path in syspaths.split(":"):
    if path != "":
      cargs.add superQuote do: "-I" & hostAbsolutePath(`path`, getProjectPath())
      sysPathDefined = true
  if not sysPathDefined:
    let clangIncludePath = getClangIncludePath()
    if clangIncludePath != "":
      cargs.add newLit("-I" & hostQuoteShell(clangIncludePath))
  result.add quote do: importcImpl(`defs`, `outputPath`, `cargs`, `files`, `importDirs`, `ignores`, `renames`, `retypes`, RenameCallback(`renameCallback`), OpirCallbacks(`opirCallbacks`), PragmasCallback(`pragmasCallback`), `forwards`)

proc hash*(n: NimNode): Hash = hash(n.treeRepr)

proc stripCommonPrefix(strs: var openArray[string]) =
  var
    stop = 0
    lastSlash = 0
    c: char
  block check:
    while true:
      for i, str in strs:
        if i == 0:
          c = str[stop]
        else:
          if str.high >= stop and str[stop] != c:
            break check
        if i == strs.high and c == DirSep:
          lastSlash = stop
      stop += 1
      if strs[0].high < stop:
        break
  for str in strs.mitems:
    str.delete(0..lastSlash)

proc getCommonPrefix(strs: openArray[string]): string =
  var
    stop = 0
    lastSlash = 0
    c: char
  block check:
    while true:
      for i, str in strs:
        if i == 0:
          c = str[stop]
        else:
          if str.high >= stop and str[stop] != c:
            break check
        if (i == strs.high and c == DirSep) or str.high == stop:
          lastSlash = stop
      stop += 1
      if strs[0].high < stop:
        break
  strs[0][0..lastSlash]

macro importcImpl*(defs, outputPath: static[string], compilerArguments, files, importDirs, ignores: static[openArray[string]], renames, retypes: static[openArray[FromTo]], renameCallback: static[RenameCallback], opirCallbacks: static[OpirCallbacks], pragmasCallback: static[PragmasCallback], forwards: static[openArray[Forward]]): untyped =
  ## Generate code from C header file. A string, `defs`, containing a header
  ## file with `#include` statements, preprocessor defines and rules, etc. to
  ## be converted is compiled with `compilerArguments` passed directly to clang.
  ## All the symbols defined in any of the `files` listed and all their
  ## dependant types will be declared. To rename a type or field pass a series
  ## of tuples to `renames`. And to declare a different type for a field in a
  ## struct pass a series of tuples to `retypes`. See the module documentation
  ## for the format. This is used by `importc` internally.
  ##
  ## See also:
  ## * `importc(varargs[untyped]) <#importc,varargs[untyped]>`_
  var
    defs = defs
    compilerArguments = compilerArguments.toSeq.toHashSet
    state = State(
      #types: newNimNode(nnkTypeSection),
      #procs: newStmtList(),
      #extraTypes: newStmtList(),
      renameCallback: renameCallback,
      pragmasCallback: pragmasCallback,
      forwards: forwards.toSeq)

  let
    projectMode = files.len == 0
    commonPrefix = if importDirs.len == 0: "/" else: importDirs.getCommonPrefix
    extraFiles = block:
      var files: HashSet[string]
      var extraIncludes: HashSet[string]
      for dir in importDirs:
        if dir in ignores: continue
        for file in dir.walkDirRec:
          block outer:
            block inner:
              for element in ignores:
                if file.isRelativeTo(element): break inner
              break outer
            continue
          files.incl file
          if projectMode and file.splitFile.ext == ".h":
            defs &= "#include \"" & file & "\"\n"
            compilerArguments.incl "-I" & file.parentDir
            extraIncludes.incl file.parentDir
            state.files.add file
      files
    cacheDir = querySetting(nimcacheDir)
    fname = cacheDir / "futhark-includes.h"
    cmd = "opir " & compilerArguments.toSeq.join(" ") & " " & fname.hostQuoteShell()
    opirHash = hash(defs) !& hash(cmd) !& hash(VERSION)
    renameCallbackSym = quote: `renameCallback`
    pragmasCallbackSym = quote: `pragmasCallback`
    opirCallbackSyms = opirCallbacks.mapIt(quote do: `it`)
    fullHash = !$(hash(nodeclguards) !& hash(noopaquetypes) !& hash(exportall) !&
      hash(generateInline) !& hash(preAnsiFuncDecl) !& hash(renames) !&
      hash(retypes) !& opirHash !&
      hash(if renameCallback.isNil: "" else: renameCallbackSym[0].symBodyHash) !&
      hash(if pragmasCallback.isNil: "" else: pragmasCallbackSym[0].symBodyHash) !&
      (if forwards.len != 0: forwards.mapIt(hash(it)).foldl(a !& b) else: hash("")) !&
      (if opirCallbackSyms.len != 0: opirCallbackSyms.mapIt(hash(it[0].symBodyHash)).foldl(a !& b) else: hash("")))
    futharkCache = if outputPath.len == 0: cacheDir / "futhark_" & fullHash.toHex & ".nim"
      elif dirExists(outputPath): outputPath / "futhark_" & fullHash.toHex & ".nim"
      else: outputPath
    opirCache = cacheDir / "opir_" & (!$opirHash).toHex & ".json"

  # Check if everything can be skipped and we can simply include our cached results
  if not projectMode and fileExists(futharkCache) and not futharkRebuild:
    hint "Using cached Futhark output: " & futharkCache
    return quote do:
      include `futharkCache`

  # Check if we have an old Opir output and the user just specified different post-processing steps
  let output =
    if fileExists(opirCache) and not opirRebuild:
      hint "Using cached Opir output: " & opirCache
      staticRead(opirCache)
    else:
      # Required for gorgeEx()/staticExec() to "act" like cmd.exe
      hostCreateDir(fname.parentDir)
      writeFile(fname, defs)
      hint "Running: " & cmdPrefix & cmd
      let opirRes = gorgeEx(cmdPrefix & cmd)
      if opirRes.exitCode != 0:
        var err = "Opir exited with non-zero exit code $1." % $opirRes.exitCode
        if opirRes.output != "":
          err.add "\nOpir output: \n" & opirRes.output
        # Seems like opir wasn't found (gorgeEx returns -1 exit code on OSError/IOError)
        if opirRes.output == "" and opirRes.exitCode == -1:
          err.add " Are you sure opir is in PATH?"
        error err
      else:
        let opirOutput = opirRes.output.strip(chars=Whitespace).splitLines
        for i in 0..<opirOutput.high:
          echo opirOutput[i]
        opirOutput[^1]


  hint "Parsing Opir output"
  # TODO: Clear out old cache files?
  var
    fut = try:
      output.parseJson
    except JsonParsingError:
      nil
  if fut == nil:
    error "Unable to parse output of opir:\n" & output

  if not fileExists(opirCache) or opirRebuild:
    hint "Caching Opir output in " & opirCache
    writeFile(opirCache, output)

  hint "Generating Futhark output"
  # Add explicit field renames
  for rename in renames:
    let oldName = rename.f.split('.')
    if oldName.len == 2:
      state.fieldRenames.mgetOrPut(oldName[0], default(Table[string, string]))[oldName[1]] = rename.t.nimIdentNormalize()
    else:
      state.renamed[oldname[0]] = rename.t.nimIdentNormalize()

  for opirCallback in opirCallbacks:
    fut = opirCallback(fut)

  hint "Gathering symbols"
  # Gather symbols from first level of hierarchy
  for node in fut:
    let name = if node.hasKey("name"): node["name"].str else: ""
    if node.hasKey("name"):
      state.addEntity(name, node)
    # This triggers an error in the example, it needs to be compiled twice for it to work
    #if node["kind"].str == "const":
    #  state.used.incl node["name"].str
    var nodeSourceFile = node["file"].str
    # uniform paths when cross-compiling
    when not defined(windows) and windowsHost:
      nodeSourceFile = nodeSourceFile.replace('\\', DirSep)
    nodeSourceFile.normalizePath
    var shouldImport = nodeSourceFile in extraFiles
    if not shouldImport:
      for file in files:
        if nodeSourceFile.endsWith file:
          shouldImport = true
          break
    if shouldImport:
      if node["kind"].str == "import":
        createImport(node, state)
      elif node.hasKey("name"):
        if not state.used.contains name:
          discard state.sanitizeName(node)
        state.used.incl name
        state.used.addUsings node
      else:
        if node["kind"].str == "enum":
          createEnum("", node, state, "")
        else:
          warning "Anonymous global: " & $node

  hint "Find all imported symbols"
  # Find all imported symbols we need
  var usedLen = 0
  while state.used.len > usedLen:
    usedLen = state.used.len
    var newUsed = initOrderedSet[string]()
    for name in state.used:
      if state.entities.hasKey(name):
        newUsed.addUsings(state.entities[name])
    for name in newUsed:
      state.used.incl name

  hint "Generate temporary names"
  # Generate temporary names to allow overriding definitions
  for name in state.used:
    if state.entities.hasKey(name):
      let saneName = if state.renamed.hasKey(name): state.renamed[name] else: state.sanitizeName(state.entities[name])
      if state.entities[name]["kind"].str notin ["proc", "var", "const"]:
        state.typeDefMap[name] = when nodeclguards: newIdentNode(saneName) else: genSym(nskType, saneName)
        state.typeNameMap[name] = when nodeclguards: newIdentNode(saneName) else:  genSym(nskType, saneName)

      if state.entities[name]["kind"].str == "typedef":
        if state.entities[name]["type"]["kind"].str == "base" and state.entities[name]["type"]["value"].str == "void":
          state.typeDefMap[name] = bindSym("void")
          state.typeNameMap[name] = bindSym("void")
    else:
      state.typeNameMap[name] = state.sanitizeName(name, Anon).ident

  hint "Add name changes"
  # Add explicit type name changes
  for retype in retypes:
    var newType = parseExpr(retype.t)
    newType.forNode(nnkIdent, (x) => state.typeNameMap.getOrDefault(x.strVal, x))
    var fieldName = retype.f.split('.')
    state.retypes.mgetOrPut(fieldName[0].nimIdentNormalize, default(Table[string, NimNode]))[fieldName[1].nimIdentNormalize] = newType

  hint "Generate Nim code"
  # Generate Nim code from Opir output with applicable post-processing
  for elem in state.used:
    if state.entities.hasKey elem:
      let
        node = state.entities[elem]
        comment = "Generated based on " & node["file"].str & ":" & $node["position"]["line"].num & ":" & $node["position"]["column"].num
      state.currentFile = node["file"].str
      case node["kind"].str:
      of "struct", "union":
        createStruct(node["name"].str, state.renamed[node["name"].str], node, state, comment)
      of "typedef":
        createTypedef(node["name"].str, node, state, comment)
      of "enum":
        createEnum(node["name"].str, node, state, comment)
      of "proc":
        createProc(elem, node, state)
      of "var":
        createVar(elem, node, state)
      of "const":
        createConst(elem, node, state, comment)
      else:
        warning "Unknown node kind: " & $node["kind"]
      #else:
      #  echo "Unknown name: ", elem

  hint "Add setting up imports"
  # Add non-dependant types and auxilary types
  var fileResult: Table[string, NimNode]
  let xIdent = newIdentNode("x")
  result = newStmtList()
  if not nodeclguards:
    result.add quote do:
      {.warning[UnusedImport]:off.}
      {.hint[XDeclaredButNotUsed]:off.}
      from macros import hint, warning, newLit, getSize
      from os import parentDir
      when not declared(ownSizeOf):
        macro ownSizeof(`xIdent`: typed): untyped = newLit(`xIdent`.getSize) # This returns negative numbers on errors instead of erroring out
  elif projectMode:
    result.add quote do:
      from os import parentDir

  for file in state.files:
    fileResult[file] = newStmtList()
    if not nodeclguards:
      fileResult[file].add quote do:
        {.warning[UnusedImport]:off.}
        {.hint[XDeclaredButNotUsed]:off.}
        from macros import hint, warning, newLit, getSize
        from os import parentDir
        when not declared(ownSizeOf):
          macro ownSizeof(`xIdent`: typed): untyped = newLit(`xIdent`.getSize) # This returns negative numbers on errors instead of erroring out
    elif projectMode:
      result.add quote do:
        from os import parentDir

    # TODO: Add exists guard
    if state.explicitImports.hasKey(file):
      for imp in state.explicitImports[file]:
        fileResult[file].add nnkImportStmt.newTree(nnkPragmaExpr.newTree(newLit(imp), nnkPragma.newTree(newIdentNode("all"))))
        fileResult[file].add nnkExportStmt.newTree(newIdentNode(imp.splitFile.name))
    if state.imports.hasKey(file):
      for imp in state.imports[file] - state.explicitImports.getOrDefault(file):
        fileResult[file].add nnkImportStmt.newTree(nnkPragmaExpr.newTree(newLit(imp), nnkPragma.newTree(newIdentNode("all"))))

    let cfile = file.changeFileExt("c")
    if fileExists(cfile):
      let
        cfile = newLit(
          if outputPath.len != 0:
            let outputDir = file.relativePath(commonPrefix).absolutePath(outputPath).parentDir
            cfile.relativePath(outputDir)
          else: cfile)
        hfile = newLit(
          if outputPath.len != 0:
            let outputDir = file.relativePath(commonPrefix).absolutePath(outputPath).parentDir
            file.relativePath(outputDir)
          else: file)
        importDir = newLit(cfile.strVal.parentDir)
      fileResult[file].add quote do:
        {.passC: "-I" & currentSourcePath().parentDir & "/" & `importDir`.}
        {.compile: `cfile`.}
  template resultAdd(file, node: untyped): untyped =
    if file == "": result.add node
    elif not fileResult.hasKey(file): result.add node
    else: fileResult[file].add node

  hint "Adding extra types"
  for key, value in state.extraTypes:
    resultAdd key, value

  hint "Adding opaque types"
  when not noopaquetypes:
    # Generate required opaque types
    for o in state.opaqueTypes:
      let
        origIdent = state.renamed[o].ident
        ident = state.typeDefMap.getOrDefault(o, origIdent)
      var file = if state.entities.hasKey(o): state.entities[o]["file"].str else: ""
      resultAdd file, state.declGuard(origIdent, quote do:
        type
          `ident`* = object)

  hint "Adding decl guards"
  when not nodeclguards:
    # Generate conditionals to define inner object types if not previously defined
    for name, defIdent in state.typeDefMap:
      if defIdent.strVal == "void": continue
      let
        origName = state.renamed[name]
        origIdent = origName.ident
        nameIdent = state.typeNameMap[name].exportMark
        file = state.entities[name]["file"].str
      state.addType file, (quote do:
          type
            `nameIdent` = (when declared(`origIdent`):
              when ownSizeof(`origIdent`) != ownSizeof(`defIdent`):
                static: warning("Declaration of " & `origName` & " exists but with different size")
              `origIdent`
            else: `defIdent`))[0]

  hint "Adding types"
  for key, value in state.types:
    resultAdd key, value

  hint "Adding second level of decl guards"
  when not nodeclguards:
    # Generate conditionals to define objects if not previously defined
    for name, defIdent in state.typeDefMap:
      if defIdent.strVal == "void": continue
      let
        origIdent = state.renamed[name].ident
        file = state.entities[name]["file"].str
      resultAdd file, state.declGuard(origIdent, quote do:
        type
           `origIdent`* = `defIdent`)

  hint "Adding generated procs"
  # Add generated procedures
  for key, value in state.procs:
    resultAdd key, value

  # Cache results
  hint "Caching Futhark output in " & futharkCache
  hostCreateDir(futharkCache.parentDir)
  writeFile(futharkCache, result.repr)

  for file, content in fileResult:
    let
      file = file.relativePath(commonPrefix).absolutePath(outputPath)
      outputDir = file.parentDir
      common = newLit(futharkCache.relativePath(outputDir))
      commonExport = newIdentNode(futharkCache.splitFile.name)
    var fileContent = quote do:
        import `common` {.all.}
        export `commonExport`
    fileContent &= content
    hint "Writing file " & file
    hostCreateDir(outputDir)
    writeFile(file.changeFileExt("nim"), fileContent.repr)

